//
// Created by vista on 2017/12/10.
//

#ifndef P_P10_H
#define P_P10_H
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>
using namespace std;

class Solution {
public:
    struct situation{
        int i;
        int j;
        char last;

        situation(int x,int y,char c){
            this->i = x;
            this->j = y;
            last = c;
        }
    };

    bool isMatch(string s, string p) {

        int i = 0 ,j = 0;

        stack<situation> situations;

        char last = '\0';

        situations.emplace(i,j,last);

        while (!situations.empty()) {

            situation situation1 = situations.top();
            situations.pop();
            i = situation1.i;
            j = situation1.j;
            last = situation1.last;

            bool need_asterisk = false;
            bool cannot = false;

            while (j < p.length()) {
                if (need_asterisk) {
                    if (p[j] == '*') {
                        ++j;
                        need_asterisk = false;
                        continue;
                    } else {
                        cannot = true;
                        break;
                    }
                }

                if (i >= s.length()) {
                    if (p[j] == '*') {
                        situations.emplace(i - 1, j + 1, last);
                        ++j;
                        continue;
                    }
                }

                if (p[j] != '*') {
                    last = p[j];
                    if ( i < s.length() && (s[i] == last || last == '.')) {
                        ++i;
                        ++j;
                    } else {
                        need_asterisk = true;
                        ++j;
                    }
                } else {
                    situations.emplace(i - 1, j + 1, last);
                    if (i < s.length() && (s[i] == last || last == '.')) {
                        ++i;
                    } else {
                        ++j;
                    }
                }
            }

            if(cannot)
                continue;

            if(i == s.length() && !need_asterisk)
                return true;
        }

        return false;
    }
};
#endif //P_P10_H
